package com.sourcetrip.algorithm.sort.count;


import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;
import com.sourcetrip.utils.Integers;

/**
 * @author: ZhouBert
 * @date: 2021/1/4
 * @description: 十大排序算法之八：计数排序（的对象比较版本，并不能比较自定义对象） --
 * 不同于前六个【基于比较的排序】，而是第一个典型的通过空间换时间的排序。
 * --
 * 限制：
 * 1.只限制于 整数排序（可以控制数组的“水平线”，完成对负整数进行排序）
 */
public class CountCustomedSortV0 extends AbstractCustomedObjectSort<Integer> {

	/**
	 * 其实挺讨巧的排序方式。
	 * 设计：
	 * 1.将 待排序中的值映射到数组中的 索引；
	 * 2.转换 为 数组的表达形式；
	 * 3.将数组的形式翻译出来
	 *
	 * @param objectArr
	 */
	@Override
	protected void sortArr(Integer[] objectArr) {

		//1.创建数组
		int max = (int) objectArr[0];
		for (int i = 1; i < objectArr.length; i++) {
			max = Math.max((int) objectArr[i], (int) max);
		}
		int[] array = new int[max + 1];
		//2.遍历，在值对应索引下填上对应的个数
		for (int i = 0; i < objectArr.length; i++) {
			array[(int) objectArr[i]]++;
		}
		//3.翻译数组
		int index = 0;
		for (int i = 0; i < array.length; i++) {
			while (array[i]-- != 0) {
				objectArr[index++] = i;
			}
		}


	}


	public static void main(String[] args) {
		Integer[] random = Integers.random(10_000_000, 1, 1_000_000);
		CountCustomedSortV0 sortV0 = new CountCustomedSortV0();
		sortV0.sortArr(random);
		boolean res = Integers.isAscOrder(random);
		System.out.println("res = " + res);
		//居然不能继承到父类 sortArr
		System.out.println("sortV0 = " + sortV0.toString());

	}
}
